// 面试题 01.02. 判定是否互为字符重排
class Solution {
public:
    int map1[26] = {0};
    int map2[26] = {0};
    bool CheckPermutation(string s1, string s2) {
        for(char e : s1) map1[e - 'a']++;
        for(char e : s2) map2[e - 'a']++;

        for(int i = 0; i < 26; i++)
        {
            if(map1[i] != map2[i]) return false;
        }
        return true;
    }
};

// 34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1, -1};
        // 找左端点
        int left = 0, right = nums.size() - 1, begin = 0;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] != target) return {-1, -1};
        else  begin = left;
        // 找右端点
        right = nums.size() - 1;
        int end = 0;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        if(nums[right] != target) return {-1, -1};
        else  end = right;
        return {begin, end};
    }
};